public class BinaryTree {
    private class Node {
        char data;           //数据域
        Node left, right;    //左孩子指针域 右孩子指针域

        public Node(char data) {
            this.data = data;
        }
    }

    private Node root;  //二叉树的根节点

    //通过扩展层序遍历进行构建
    //"1234#5#6###7"
    public BinaryTree(String s) {
        root = create(s, 0);
    }

    private Node create(String s, int i) {
        if (s.charAt(i) == '#') {
            return null;
        } else {
            Node node = new Node(s.charAt(i));
            int leftChildIndex = 2 * i + 1;
            int rightChildIndex = 2 * i + 2;
            if (leftChildIndex < s.length()) {
                node.left = create(s, leftChildIndex);
            }
            if (rightChildIndex < s.length()) {
                node.right = create(s, rightChildIndex);
            }
            return node;
        }
    }

    //递归先序遍历
    public void preOrder() {
        ArrayList<Character> list = new ArrayList<>();
        preOrder(root, list);
        System.out.println(list);
    }

    private void preOrder(Node node, ArrayList<Character> list) {
        if (node == null) {
            return;
        }
        list.add(node.data);
        preOrder(node.left, list);
        preOrder(node.right, list);
    }

    public void inOrder() {
        ArrayList<Character> list = new ArrayList<>();
        inOrder(root, list);
        System.out.println(list);
    }

    private void inOrder(Node node, ArrayList<Character> list) {
        if (node == null) {
            return;
        }
        inOrder(node.left, list);
        list.add(node.data);
        inOrder(node.right, list);
    }

    public void postOrder() {
        ArrayList<Character> list = new ArrayList<>();
        postOrder(root, list);
        System.out.println(list);
    }

    private void postOrder(Node node, ArrayList<Character> list) {
        if (node == null) {
            return;
        }
        postOrder(node.left, list);
        postOrder(node.right, list);
        list.add(node.data);
    }

    public void levelOrder() {
        ArrayList<Character> list = new ArrayList<>();
        ArrayQueue<Node> queue = new ArrayQueue<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            Node cur = queue.poll();
            list.add(cur.data);
            if (cur.left != null) {
                queue.offer(cur.left);
            }
            if (cur.right != null) {
                queue.offer(cur.right);
            }
        }

        System.out.println(list);
    }

}